﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你⼀个m × n的矩阵mat和⼀个整数k，请你返回⼀个矩阵answer，其中每个answer[i][j]是所有满⾜下述条件的元素mat[r][c]的和：
//• i - k <= r <= i + k, 
//• j - k <= c <= j + k且(r, c)在矩阵内。

//eg: 输⼊：mat =  [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 1   
//    输出： [[12, 21, 16], [27, 45, 33], [24, 39, 28]]

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> matrixBlockSum(vector<vector<int>> mat,int k)
{
	int m = mat.size(), n = mat[0].size();

	vector<vector<int>> dp(m + 1, vector<int>(n + 1));// 1. 预处理前缀和矩阵
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];// 2. 使⽤
		}
	}

	vector<vector<int>> ret(m, vector<int>(n));
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
			int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
			ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +dp[x1 - 1][y1 - 1];
		}
	}
	return ret;
}

int main()
{
	vector<vector<int>> mat = { {1, 2, 3},{4, 5, 6},{7, 8, 9 } };
	int k = 1;
	vector<vector<int>> answer = matrixBlockSum(mat, k);
	for (auto n : answer)
	{
		for (auto elem : n)
		{
			cout << elem << ' ';
		}
		cout << endl;
	}

	return 0;
}